/**
 * 
 */
package zhoujian.oj.leetcode;

import java.util.HashMap;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;


/**
 * @author hyper
 * @email zjkermit@gmail.com
 * @date Dec 9, 2013
 * @version 1.0
 * @description Given a string, find the length of the longest substring 
 * 				without repeating characters. 
 * 				For example, the longest substring without repeating letters 
 * 				for "abcabcbb" is "abc", which the length is 3. 
 * 				For "bbbbb" the longest substring is "b", with the length of 1.
 */
public class LongestSubstrWithoutRepeatingChar {
	
	private static Logger log = LoggerFactory.getLogger(LongestSubstrWithoutRepeatingChar.class);
	
	public static int lengthOfLongestSubstring(String s) {
		return asciiHandle(s);
	}
	
	public static int asciiHandle(String s) {
		int start = 0;
		int res = 0;  
        int[] pos = new int[256];  
        for(int i = 0; i < 256; i++)  
            pos[i] = -1;  
        for(int i = 0; i < s.length(); i++){  
            char temp = s.charAt(i);  
            if(start <= pos[(int)temp]){  
                res = Math.max(res, i - start);  
                start = pos[(int)temp] + 1;  
            }  
            pos[(int)temp] = i;  
        }  
        res = Math.max(res, s.length() - start);  
        return res;  
	}
	
	public static int hashHandle(String s) {
		if (s == null || s.equals("")) {
			return 0;
		}
		
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		int maxLen = 0;
		int start = 0;
		
		for (int i = 0; i < s.length(); i++) {
			log.debug("======================= > {}", i);
			log.debug("s.charAt(i) = {}", s.charAt(i));
			if (map.get(s.charAt(i)) != null && map.get(s.charAt(i)) >= start) {
				log.debug("map.get(s.charAt(i)) = {}", map.get(s.charAt(i)));
				log.debug("start = {}", start);
				maxLen = Math.max(maxLen, i - start);
				log.debug("maxLen = {}", maxLen);
				start = map.get(s.charAt(i)) + 1;
				log.debug("start = {}", start);
			} 
			map.put(s.charAt(i), i);
		}
		
		return Math.max(maxLen, s.length() - start);
	}
	
	public static void main(String[] args) {
		//assert lengthOfLongestSubstring("abcabcbb") == 3;
		//assert lengthOfLongestSubstring("bbbbb") == 1;
		//assert lengthOfLongestSubstring("") == 0;
		//assert lengthOfLongestSubstring(null) == 0;
		assert lengthOfLongestSubstring("wlrbbmqbhcdarzowkkyhiddqscdxrjmowfrxsjybldbefsarcbynecdyggxxpklorellnmpapqfwkhopkmco") == 12;
		assert lengthOfLongestSubstring("qopubjguxhxdipfzwswybgfylqvjzhar") == 12;
	}

}
